package fun.coding.leetcode;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;
import java.util.Stack;

public class BinaryTreeInorderTraversal {

	public static void main(String[] args) {
		BinaryTreeInorderTraversal btit = new BinaryTreeInorderTraversal();
		/*      1
		 *    2   3
		 *  4   5
		 *  in order -> 4 2 5 1 3
		 */
		TreeNode root = new TreeNode(1);
		root.left = new TreeNode(2);
		root.right = new TreeNode(3);
		root.left.left = new TreeNode(4);
		root.left.right = new TreeNode(5);
		
		List<Integer> res = btit.inorderTraversal(root);
		
		for (int i : res) {
			System.out.println(i);
		}
	}

	public List<Integer> inorderTraversal(TreeNode root) {
		Stack<TreeNode> stack = new Stack<TreeNode>();
		List<Integer> res = new LinkedList<Integer>();
		
		if (root == null) return res;
		// an extra pointer
		TreeNode cur = root;
		while (!stack.isEmpty() || cur != null) {
			if (cur != null) {
				stack.push(cur);
				cur = cur.left;
			} else {
				TreeNode t = stack.pop();
				res.add(t.val);
				cur = t.right;
			}
		}
		return res;
	}
	
	public List<Integer> inorderTraversalUsingSet(TreeNode root) {
		List<Integer> res = new LinkedList<Integer>();
		
		if (root == null) return res;
		
		Stack<TreeNode> s = new Stack<TreeNode>();
		Set<TreeNode> processed = new HashSet<TreeNode>();
		
		s.push(root);
		
		while (!s.isEmpty()) {
			TreeNode cur = s.pop();
			if (processed.contains(cur)) {
				res.add(cur.val);
				continue;
			}
			
			if (cur.left == null && cur.right == null) {
				res.add(cur.val);
			} else {
				if (cur.right != null) s.push(cur.right);
				s.push(cur);
				processed.add(cur);
				if (cur.left != null) s.push(cur.left);
			}
		}
		return res;
	}
	
}
